package com.dhj.springSprint100;

import java.util.ArrayList;
import java.util.List;

public class SpiralOrder {
    public static void main(String[] args) {
        System.out.println(spiralOrderA(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
    }

    public static List<Integer> spiralOrderA(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        // 矩阵为空的情况
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        int top = 0;                   // 上边界
        int bottom = matrix.length - 1; // 下边界
        int left = 0;                  // 左边界
        int right = matrix[0].length - 1; // 右边界

        while (top <= bottom && left <= right) {
            // 从左到右遍历当前上边界
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++; // 上边界下移

            // 从上到下遍历当前右边界
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--; // 右边界左移

            // 从右到左遍历当前下边界（如果 top <= bottom）
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--; // 下边界上移
            }

            // 从下到上遍历当前左边界（如果 left <= right）
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++; // 左边界右移
            }
        }

        return result;
    }

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        // 初始化边界
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        // 定义方向：右 -> 下 -> 左 -> 上
        int[] directions = {0, 1, 2, 3}; // 0: 右, 1: 下, 2: 左, 3: 上
        int dirIndex = 0; // 当前方向索引

        while (top <= bottom && left <= right) {
            result.addAll(spiralOrder2(matrix, top, bottom, left, right, directions[dirIndex]));

            // 根据方向调整边界
            switch (directions[dirIndex]) {
                case 0: top++; break;   // 右，收缩上边界
                case 1: right--; break; // 下，收缩右边界
                case 2: bottom--; break; // 左，收缩下边界
                case 3: left++; break;  // 上，收缩左边界
            }

            // 更新方向
            dirIndex = (dirIndex + 1) % 4;
        }

        return result;
    }

    public static List<Integer> spiralOrder2(int[][] matrix, int top, int bottom, int left, int right, int direction) {
        List<Integer> result = new ArrayList<>();

        switch (direction) {
            case 0: // 从左到右
                for (int i = left; i <= right; i++) {
                    result.add(matrix[top][i]);
                }
                break;
            case 1: // 从上到下
                for (int i = top; i <= bottom; i++) {
                    result.add(matrix[i][right]);
                }
                break;
            case 2: // 从右到左
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                break;
            case 3: // 从下到上
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                break;
        }

        return result;
    }
}
